[TJOI2015]组合数学

2020-02-02
#idea #动态规划Dp #网络流 #Dilworth
TJOI

题意

在$n*m$的网格中每个格子有一些财宝，每次从左上向右下行走，经过的时候如果格子中有财宝则可以捡起一个

问最小次数，捡完所有财宝

题解

如果把矩阵看成图，显然是个DAG，答案就是最小链覆盖

考虑Dilworth，最小链覆盖=最长反链

反链一定从左下->右上，Dp即可

调试记录

最后要输出Max，可以不经过(1,m)的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
const int maxn = 1005;
using namespace std;
int T, a[maxn][maxn], n, m;
LL f[maxn][maxn], Max[maxn][maxn];
int main(){
	scanf("%d", &T);
	while (T--){
		memset(f, 0, sizeof f);
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) scanf("%d", a[i] + j);
		for (int i = n; i >= 1; i--)
			for (int j = 1; j <= m; j++){
				f[i][j] = Max[i + 1][j - 1] + a[i][j];
				Max[i][j] = max(max(Max[i + 1][j], Max[i][j - 1]), f[i][j]);
			}
		printf("%lld\n", Max[1][m]);
	}
	return 0;
}